iT邦幫忙

2024 iThome 鐵人賽

DAY 9
0

貪婪演算法(Greedy Algorithm) 又稱作貪心法,簡單來說,此演算法是在每一個步驟使用貪心原則,只考慮當前情況的前提下選擇最優解法。其精神在於「只做眼前的最佳解」,它將需求解的問題分解成許多子問題,並且在解決一個個子問題時皆選用當下的最佳解法,並非考慮到全局。所以即使貪婪演算法的宗旨在透過這樣的解決方式,使整個問題能尋求最好的解法。但往往因為未顧及全局只選擇當下最優解,未必在各類型問題上會使最後求得的解法是最好的。貪婪法這樣一步步解決子問題的解法只能在部分求滿足約束條件的問題上較為可行,例如:找零錢問題。以下將進行找零錢問題的範例說明:


範例說明
https://ithelp.ithome.com.tw/upload/images/20240919/20168781s1OY5CovEi.png
在日常生活中我們時常會遇到找零錢問題,當我們是情境中的店員並發生以下這種情況時,我們往往會選擇找一個50元、一個10元、一個5元和一個1元,並非找給客人66個1元。
https://ithelp.ithome.com.tw/upload/images/20240919/20168781zSGuGpiX9Z.png
像是這樣的情況套用在程式上,就是因為我們使用了「貪婪演算法」,所以一剛開始根據66元這種數字,我們會先按照50元、10元、5元和1元這種面額升序的前提來找錢給客人,這樣的思維邏輯就是貪婪演算法喔!


優點:

  • 簡單且高效:貪婪演算法通常較容易實現,並且在時間複雜度上也相對較低。
  • 應用廣泛:適用於一些典型的問題,如找零錢問題、最小生成樹、霍夫曼編碼等。
  • 逐步決策:每次做出當前最佳選擇,不需要全局分析,節省時間和計算資源。

缺點:

  • 不一定保證最優解:貪婪演算法因為每次都選擇局部最優解,無法確保最終得到全局最優解,特別是問題較為複雜時。
  • 依賴問題特性:它只在某些特定問題中有效,並不是所有問題都能用貪婪策略解決。
  • 可能忽略未來影響:只考慮當下最佳選擇,可能導致後續選擇變得困難或次優。

參考資料:

  1. 演算法學習筆記-貪婪演算法 - Medium by Sean Chou
  2. 貪婪演算法 - HackMD by Maxlight
  3. 胡昭民 (2023)。《圖解資料結構 × 演算法:運用 Python 結合 ChatGPT 輔助驗證及寫程式》。新北:博碩文化。

上一篇
Day8 Dynamic Programming 題目3:139. Word Break
下一篇
Day10 Greedy Algorithm題目1:121. Best Time to Buy and Sell Stock
系列文
Java刷題B:Leetcode Top 100 Liked30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言